/*
  Name: 二叉链表实现二叉树 
  Copyright: 
  Author: 
  Date:
  Description: 
*/

#ifndef BINTREE_H_INCLUDED
#define BINTREE_H_INCLUDED

#include <stdlib.h>
#include "ds.h"

//数据元素的缺省类型用char 
#ifndef ElemType
#define ElemType char
#define ELEMTYPE_TAG
#endif
/*下面使用TElemType如同ElemType*/
#define TElemType ElemType

///////////////////////////////////////////////////////////
// 二叉链表类型 
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针 
} BiTNode, *BiTree;


///////////////////////////////////////////////////////////
// 二叉链表的基本操作

//新建二叉链表结点
BiTree MakeNode(TElemType e, BiTree lch, BiTree rch)
{
    BiTree p = (BiTree)malloc(sizeof(BiTNode));
    p->data = e;
    p->lchild = lch;
    p->rchild = rch;
    return p;
}

//按先序次序输入二叉树中的结点值(字符)构造二叉树 
Status CreateBiTree(BiTree &T)
{
    char ch;
    read(ch); // NOTE: 这里用字符类型
    if( ch==' ' ) //空格代表空指针
        T = 0;
    else {
        //建立结点 
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ch; 
        //-------------------------------------
        // TODO (#1#):建立左子树和右子树
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
        //-------------------------------------
    }
    return OK;
}

//销毁二叉树
Status DestroyBiTree(BiTree &T)
{
    //-------------------------------------
    // TODO (#1#): 销毁二叉树,释放所有结点 
    return ERROR;
    //-------------------------------------
} 

//先序遍历二叉树T，对每个结点数据调用Visit函数
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{
    //-------------------------------------
    // TODO (#1#): 先序遍历二叉树
    return ERROR;
    //-------------------------------------
}

//中序遍历二叉树T，对每个结点数据调用Visit函数
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{
    //-------------------------------------
    // TODO (#1#): 中序遍历二叉树
    return ERROR;
    //-------------------------------------
}

//后序遍历二叉树T，对每个结点数据调用Visit函数
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{
    //-------------------------------------
    // TODO (#1#): 后序遍历二叉树
    return ERROR;
    //-------------------------------------
}

//按层次顺序遍历二叉树T，对每个结点数据调用Visit函数
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{
    //-------------------------------------
    // TODO (#1#): 按层次遍历二叉树
    return ERROR;
    //-------------------------------------
}

//以直观方式打印二叉树
void PrintTree(BiTree t, int level=0)
{
    int i;
    if(t) {
        PrintTree(t->rchild, level+1);
        for(i=0; i<level; i++) printf("    ");
        write(t->data); write('\n');
        PrintTree(t->lchild, level+1);
    }
}

//取消缺省类型的定义以免影响其它部分 
#ifdef ELEMTYPE_TAG
#undef ElemType
#undef ELEMTYPE_TAG
#endif

#endif //BINTREE_H_INCLUDED

